Afin de déterminer la complexité de l'algorithme de Kruskal, nous allons diviser chaque partie. Pour commencer, posons m le nombre d'arêtes et n le nombre de sommets. La priority queue est en $O(m
\times \log(n))$\footnote{$m$ est le nombre d'arêtes et $n$ le nombre de nœuds dans le graphe}. Au niveau des cluster, nous sommes en $O(m\times \log(n))$ également (ces complexités théoriques sont trouvées dans le livre DSAJ-5). Nous avons donc du $O(m\times \log(n))$ pour cet algorithme.\\


Nous allons maintenant vérifier notre complexité au moyen de tests. Nous lançons $500$ fois le programme et nous prenons la moyenne du temps d'exécution de l'algorithme de Kruskal. Nous avons pour celà plusieurs fichiers contenant de $50$ à $1000$ ($=$ villes). Les résultats des temps d'exécution sont repris dans le tableau ci-dessous : 

\begin{center}
\begin{tabular}{|c|c|c|}
  \hline
  Nombre de sommets & 	Nombre d'arêtes  & 			Résultat moyen (en sec)  			\rule[-7pt]{0pt}{20pt} \\
  \hline 
 50   &    49  	&	  	0.000158736			 \rule[-7pt]{0pt}{20pt} \\
 50   &    75  	&		0.000185196				\rule[-7pt]{0pt}{20pt}  \\
 250  &   249  	&    	0.000337668 			\rule[-7pt]{0pt}{20pt}  \\
 250  &   1273  &    	0.001566504			\rule[-7pt]{0pt}{20pt}  \\
 500  &   499   & 		0.000708878				\rule[-7pt]{0pt}{20pt}  \\
 500  &   1250  &    	0.001811700				\rule[-7pt]{0pt}{20pt}  \\
 1000 &   8433  &    	0.042869288			\rule[-7pt]{0pt}{20pt}  \\
  \hline
\end{tabular}
\end{center}

En analysant les résultats du tableau on peut vérifier que nos valeurs suivent la complexité obtenue à une constante près. Dès lors, doubler le nombre d'arêtes double le temps tandis que doubler le nombre de sommet n'a qu'un influence minime voire négligeable sur le temps. Bien sur ces temps sont surtout là pour montrer que la complexité dépend du nombre d'arêtes ainsi que du nombre de sommets et pas que de l'un ou l'autre. Nous voyons également que la complexité n'est pas linéaire au niveau des sommets ni quadratique sur un des deux paramètres.